import java.util.HashMap;
import java.util.Map;

public class Test48_13 {
    /*
    动态规划解析：
    状态定义： 设动态规划列表 dp ，dp[j] 代表以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度。
    转移方程： 固定右边界 j ，设字符 s[j] 左边距离最近的相同字符为 s[i] ，即 s[i] =s[j] 。
    当 i<0 ，即 s[j] 左边无相同字符，则 dp[j] = dp[j-1] + 1；
    当 dp[j - 1] < j - i ，说明字符 s[i] 在子字符串 dp[j−1] 区间之外 ，则 dp[j] = dp[j - 1] + 1
    当 dp[j−1]≥j−i ，说明字符s[i] 在子字符串 dp[j−1] 区间之中 ，则 dp[j]的左边界由 s[i]决定，即 dp[j]=j−i ；

     */
    public static int lengthOfLongestSubstring(String s){
        Map<Character,Integer> dic = new HashMap<>();
        int res = 0;
        int temp = 0;//辅助变量
        for(int i = 0; i< s.length();i++){
            //如果i没有重复的字符，那么将会一直返回 -1
            int j = dic.getOrDefault(s.charAt(i),-1);//如果i存在则获取i的索引，如果不存在则返回-1；
            dic.put(s.charAt(i),i);//放入i 和i的索引
            //如果小于目前不重复字符串的长度，那么temp++，如果大于当前不重复字符串的长度，则返回i-j；
            temp = temp < i-j? temp +1:i-j;
            res = Math.max(res,temp);
        }
        return res;
    }

    public static int lengthOfLongestSubstring2(String s){
        Map<Character,Integer> dic = new HashMap<>();
        int res = 0;
        int[] dp = new int[s.length()];
        dp[0] = 1;
        dic.put(s.charAt(0),0);
        for(int i = 1; i< s.length();i++){
            int j = dic.getOrDefault(s.charAt(i),-1);
            dic.put(s.charAt(i),i);
            if (dp[i-1] >= i-j)//说明有重复的字符出现
                dp[i] = i-j;
            else dp[i] = dp[i-1]+1;//还没有出现重复的字符
            res = Math.max(dp[i],res);
        }
        return res;
    }

    public static int lengthOfLongestSubstring3(String s) {
        //使用哈希表map统计各字符最后一次出现的索引位置
        Map<Character, Integer> map = new HashMap<>();
        //划定当前窗口的坐标为(start,j],左闭右闭,start的初始值为-1,而非0
        int start = -1;
        int res = 0;
        for (int j = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j)))
                //当字符在map中已经存储时，需要判断其索引值index和当前窗口i的大小以确定是否需要对i进行更新:
                //当index>i时，i更新为当前的index,否则保持不变。
                start = Math.max(start, map.get(s.charAt(j)));//更新j
            //更新map
            map.put(s.charAt(j), j);
            //如果j-start的长度大于之前存的长度
            res = Math.max(j-start,res);//更新 结果
        }
        return res;
    }

    public static int lengthOfLongestSubstring4(String s){
        // 记录每个字母出现的最后位置
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int left = 0;//左边
        int right = 0;//右边界
        int res = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            // 当前值已经出现过了，更新左边界
            if (hashMap.containsKey(ch)) {
                // 另 left = 当前值最后一次出现的地方 + 1 ，使得[left,right]无重复值
                // 需要取较大值
                left = Math.max(left, hashMap.get(ch) + 1);
            }
            //更新最后出现下标
            hashMap.put(ch, right);
            // [left,right]的长度
            res = Math.max(res, right - left + 1);
            right++;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
        System.out.println(lengthOfLongestSubstring2("abcabcbb"));
        System.out.println(lengthOfLongestSubstring3("abcabcbb"));
        System.out.println(lengthOfLongestSubstring4("abcabcbb"));
    }
}
